package com.jxm.heap;

/**
 * @Author: jxm
 * @Description: 堆API设计（完全二叉树）
 * 1、如果一个结点的位置为k，则它的父结点的位置为[k/2],而它的两个子结点的位置则分别为2k和2k+1。这样，在不
 * 使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动：从a[k]向上一层，就令k等于k/2,向下一层就
 * 令k等于2k或2k+1。
 * 2、每个结点都大于或等于它的两个子结点
 * @Date: 2022/7/1 15:54
 * @Version: 1.0
 */
public class Heap <T extends Comparable<T>> {

    private T[] items; //用来存储元素的数组
    private int N; //记录堆中元素的个数

    public Heap(int capacity){
        this.items = (T[]) new Comparable[capacity+1];
        this.N = 0;
    };

    /**
     * 判断堆中索引i处的元素是否小于索引j处的元素
     * @param i
     * @param j
     * @return
     */
    private boolean less(int i,int j){
        return items[i].compareTo(items[j]) < 0;
    }

    /**
     * 交换堆中i索引和j索引处的值
     * @param i
     * @param j
     */
    private void exch(int i,int j){
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    /**
     * 删除堆中最大的元素,并返回这个最大元素
     * @return
     */
    public T delMax(){
        T max = items[1];
        //交换索引1从的元素和最大索引从的元素，让完全二叉树中最右侧的元素变为临时根结点
        exch(1,N);
        //最大索引赵的元素删除掉
        items[N] = null;
        //  元素个数-1
        N--;
        //通过下沉调整堆，让堆重新有序
        sink(1);
        return max;
    }

    /**
     * 往堆中插入一个元素
     * @param t
     */
    public void insert(T t){
        //++N:在这里表示被执行前+1
        //N++:在这里表示执行后i的值+1
        items[++N] = t;
        swim(N);
    }

    /**
     * 使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
     * @param k
     */
    private void swim(int k){
        //通过循环，不断的比较当前结点的值和其父结点的值，如果发现父结点的值比当前结点的值小，则交换位置
        while (k>1){
            //比较当前结点和父结点
            if(less(k/2,k)){
                exch(k/2,k);
            }
            k = k/2;
        }

    }

    /**
     * 使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
     * @param k
     */
    private void sink(int k){
        //通过循环不断的对比当前k结点和其左子结点2*k以及右子结点2k+1处中的较大值的元素大小，如果当前结点小，则需要交换位置
        while (2*k<=N){
            //获取当前结点的子结点中较大结点
            int max;//记录较大结点所在索引
            if(2*k+1<=N){ //说明有右子结点
                if(less(2*k,2*k+1)){
                    max = 2*k+1;
                }else{
                    max = 2*k;
                }
            }else{
                max = 2*k;
            }

            //比较当前结点和较大结点的值
            if(!less(k,max)){
                break;
            }
            //交换k索引处的值和max索引处的值
            exch(k,max);

            //变换k的值；
            k = max;
        }

    }

}
